package com.datastructure.test.minestnumberofrotatearray;

public class MinNumberOfRotateArray {

    public static void main(String[] args) {
        int[] data = {3,4,5,1,2};
        MinNumberOfRotateArray minNumberOfRotateArray = new MinNumberOfRotateArray();
        minNumberOfRotateArray.minNumberInRotateArray(data);
    }

    public int minNumberInRotateArray(int [] array) {
        quickSort(array,0,array.length-1);
        return array[0];
    }

    public static void quickSort(int[] arrays, int low, int hi) {

        if (low < hi) {
            // 求每次分治的分割线
            int divideIndex = getDivideIndex(arrays, low, hi);
            // 再递归分别对分割的俩个子数组进行递归排序
            quickSort(arrays, low, divideIndex - 1);
            quickSort(arrays, divideIndex + 1, hi);
        }
    }

    public static int getDivideIndex(int[] arrays, int low, int hi) {
        // 设定arrays[low]为基准值,从右到左移动hi,找到大于第一个大于基准值的数字。
        // 从左向右移动low指针,找到第一个小于基准值的数,交换low和high位置上的值
        // 直到low=high的时候，将基准值填入arrays[low]
        int baseValue = arrays[low];
        int oldLow = low;
        while (low < hi) {
            while (low < hi && arrays[hi] >= baseValue) {
                hi--;
            }
            while (low < hi && arrays[low] <= baseValue) {
                low++;
            }
            if (low < hi) {
                swap(arrays, low, hi);
            }
        }
        if (low == hi) {
            arrays[oldLow] = arrays[low];
            arrays[low] = baseValue;
        }
        return low;
    }

    public static void swap(int[] arrays, int low, int high) {
        int temp = 0;
        temp = arrays[low];
        arrays[low] = arrays[high];
        arrays[high] = temp;
    }
}
